package RushHour;
import java.util.*;

/**
 * This is the class for representing a single state of the rush hour
 * puzzle.  Methods are provided for constructing a state, for
 * accessing information about a state, for printing a state, and for
 * expanding a state (i.e., obtaining a list of all states immediately
 * reachable from it).
 * <p>
 * Every car is constrained to only move horizontally or vertically.
 * Therefore, each car has one dimension along which it is fixed, and
 * another dimension along which it can be moved.  This variable
 * dimension is stored here as part of the state.  A link to the
 * puzzle with which this state is associated is also stored.
 * Note that the goal car is always assigned index 0.  
 * <p>
 * To make it easier to use <tt>State</tt> objects with some of the
 * data structures provided as part of the Standard Java Platform, we
 * also have provided <tt>hashCode</tt> and <tt>equals</tt> methods.
 * You probably will not need to access these methods directly, but
 * they are likely to be used implicitly if you take advantage of the
 * Java Platform.  These methods define two <tt>State</tt> objects to
 * be equal if they refer to the same <tt>Puzzle</tt> object, and if
 * they indicate that the cars have the identical variable positions
 * in both states.  The hashcode is designed to satisfy the general
 * contract of the <tt>Object.hashCode</tt> method that it overrides,
 * with regard to the redefinition of <tt>equals</tt>.
 */
public class State {

	private Puzzle puzzle;

	private int varPos[];

	String reachedByMove;

	/**
	 * The main constructor for constructing a state.  You probably
	 * will never need to use this constructor.
	 *
	 *   @param puzzle the puzzle that this state is associated with
	 *   @param varPos the variable position of each of the cars in this state
	 */
	public State(Puzzle puzzle, int varPos[]) {
		this.puzzle = puzzle;
		this.varPos = varPos;
		computeHashCode();
		reachedByMove = "";
	}

	public State(Puzzle puzzle, int varPos[], String move) {
		this(puzzle, varPos);
		reachedByMove = move;
	}

	/** Returns true if and only if this state is a goal state. */
	public boolean isGoal() {
		return (varPos[0] == puzzle.getGridSize() - 1);
	}

	/** Returns the variable position of car <tt>v</tt>. */
	public int getVariablePosition(int v) {
		return varPos[v];
	}

	/** Returns the puzzle associated with this state. */
	public Puzzle getPuzzle() {
		return puzzle;
	}

	/** Prints to standard output a primitive text representation of the state. */
	public void print(boolean printBoard) {

		System.out.print(reachedByMove+" ");
		
		if (!printBoard)
			return;
		
		System.out.println();
		int grid[][] = getGrid();
		int gridsize = puzzle.getGridSize();

		System.out.print("+-");
		for (int x = 0; x < gridsize; x++) {
			System.out.print("--");
		}
		System.out.println("+");

		for (int y = 0; y < gridsize; y++) {
			System.out.print("| ");
			for (int x = 0; x < gridsize; x++) {
				int v = grid[x][y];
				if (v < 0) {
					System.out.print(". ");
				} else {
					char c = puzzle.getCarName(v);
					System.out.print(c + " ");
				}
			}
			System.out.println((puzzle.getCarOrient(0) || y != puzzle
					.getFixedPosition(0)) ? "|" : (isGoal() ? ">" : " "));
		}

		System.out.print("+-");
		for (int x = 0; x < gridsize; x++) {
			System.out.print((!puzzle.getCarOrient(0) || x != puzzle
					.getFixedPosition(0)) ? "--" : (isGoal() ? "v-" : " -"));
		}
		System.out.println("+");

	}

	/**
	 * Computes a grid representation of the state.  In particular, an
	 * nxn two-dimensional integer array is computed and returned,
	 * where n is the size of the puzzle grid.  The <tt>(i,j)</tt>
	 * element of this grid is equal to -1 if square <tt>(i,j)</tt> is
	 * unoccupied, and otherwise contains the index of the car
	 * occupying this square.  Note that the grid is recomputed each
	 * time this method is called.
	 */
	public int[][] getGrid() {
		int gridsize = puzzle.getGridSize();
		int grid[][] = new int[gridsize][gridsize];

		for (int i = 0; i < gridsize; i++)
			for (int j = 0; j < gridsize; j++)
				grid[i][j] = -1;

		int num_cars = puzzle.getNumCars();

		for (int v = 0; v < num_cars; v++) {
			boolean orient = puzzle.getCarOrient(v);
			int size = puzzle.getCarSize(v);
			int fp = puzzle.getFixedPosition(v);
			if (v == 0 && varPos[v] + size > gridsize)
				size--;
			if (orient) {
				for (int d = 0; d < size; d++)
					grid[fp][varPos[v] + d] = v;
			} else {
				for (int d = 0; d < size; d++)
					grid[varPos[v] + d][fp] = v;
			}
		}
		return grid;

	}

	/**
	 * Computes all of the states immediately reachable from this
	 * state and returns them as an array of states.  You probably
	 * will not need to use this method directly, since ordinarily you
	 * will be expanding <tt>Node</tt>s, not <tt>State</tt>s.
	 */
	public State[] expand() {
		int gridsize = puzzle.getGridSize();
		int grid[][] = getGrid();
		int num_cars = puzzle.getNumCars();

		ArrayList<State> new_states = new ArrayList<State>();

		String move = "";
		for (int v = 0; v < num_cars; v++) {
			char vName = getPuzzle().getCarName(v);
			int p = varPos[v];
			int fp = puzzle.getFixedPosition(v);
			boolean orient = puzzle.getCarOrient(v);
			for (int np = p - 1; np >= 0
					&& (orient ? grid[fp][np] : grid[np][fp]) < 0; np--) {
				int[] newVarPos = (int[]) varPos.clone();
				newVarPos[v] = np;
				String direction = "";
				if (np > p) {
					direction = orient ? "D" : "R";
				} else {
					direction = orient ? "U" : "L";
				}
				move = vName + direction + Math.abs(np - p);
				new_states.add(new State(puzzle, newVarPos, move));
			}

			int carsize = puzzle.getCarSize(v);
			for (int np = p + carsize; (np < gridsize && (orient ? grid[fp][np]
					: grid[np][fp]) < 0)
					|| (v == 0 && np == gridsize); np++) {
				int[] newVarPos = (int[]) varPos.clone();
				int npCpoy = np - carsize + 1;
				newVarPos[v] = npCpoy;
				String direction = "";
				if (npCpoy > p) {
					direction = orient ? "D" : "R";
				} else {
					direction = orient ? "U" : "L";
				}
				move = vName + direction + Math.abs(npCpoy - p);
				new_states.add(new State(puzzle, newVarPos, move));
			}
		}

		puzzle.incrementSearchCount(new_states.size());

		return (State[]) new_states.toArray(new State[0]);
	}

	private int hashcode;

	private void computeHashCode() {
		hashcode = puzzle.hashCode();
		for (int i = 0; i < varPos.length; i++)
			hashcode = 31 * hashcode + varPos[i];
	}

	/**
	 * Returns a hash code value for this <tt>State</tt> object.
	 * Although you probably will not need to use it directly, this
	 * method is provided for the benefit of hashtables given in the
	 * Java Platform.  See documentation on <tt>Object.hashCode</tt>,
	 * which this method overrides, for the general contract that
	 * <tt>hashCode</tt> methods must satisfy.
	 */
	@Override
	public int hashCode() {
		return hashcode;
	}

	/**
	 * Returns <tt>true</tt> if and only if this state is considered
	 * equal to the given object.  In particular, equality is defined
	 * to hold if the given object is also a <tt>State</tt> object, if
	 * it is associated with the same <tt>Puzzle</tt> object, and if
	 * the cars in both states are in the identical positions.  This
	 * method overrides <tt>Object.equals</tt>.
	 */
	public boolean equals(Object o) {
		State s;
		try {
			s = (State) o;
		} catch (ClassCastException e) {
			return false;
		}
		if (hashcode != s.hashcode || !puzzle.equals(s.puzzle))
			return false;

		for (int i = 0; i < varPos.length; i++)
			if (varPos[i] != s.varPos[i])
				return false;
		return true;
	}
}
